package offer;
//合并两个排序的链表
public class T17 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = null;
        ListNode temp = null;
        while (list1!=null&&list2!=null) {
              if (list1.val<list2.val) {
                  if (head==null) {
                      head = list1;
                      temp = list1;
                  } else {
                      temp.next = list1;
                      temp = list1;
                  }
                  list1 = list1.next;
              }else {
                  if (head==null) {
                      head = list2;
                      temp = list2;
                  } else {
                      temp.next = list2;
                      temp = list2;
                  }
                  list2 = list2.next;
              }
          }
        while (list1!=null) {
            if (head==null) {
                head = list1;
                temp = list1;
            }else {
                temp.next = list1;
            }
            temp = list1;
            list1 = list1.next;
        }
        while (list2!=null) {
            if (head==null) {
                head = list2;
                temp = list2;
            }else {
                temp.next = list2;
            }
            temp = list2;
            list2 = list2.next;
        }
        return head;
    }
    public void test(){
        ListNode listNode1 = new  ListNode(1);
        ListNode listNode2 = new  ListNode(2);
        ListNode listNode3 = new  ListNode(3);
        ListNode listNode4 = new  ListNode(4);
        ListNode listNode5 = new  ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        ListNode listNode= Merge(listNode1,null);
        print(listNode);
    }
    public void print(ListNode listNode){
        if (listNode==null) return;;
        System.out.println(listNode.val);
        print(listNode.next);

    }
    public static void main ( String[] args) {
        new T17().test();

    }

}
